package _1894_Find_the_Student_that_Will_Replace_the_Chalk;

/**
 * Date: 2021/9/10 9:25
 * Content:
 * 执行用时：3 ms, 在所有 Java 提交中击败了28.80%的用户
 * 内存消耗：51.1 MB, 在所有 Java 提交中击败了93.19%的用户
 */
public class Solution {

    public int chalkReplacer(int[] chalk, int k) {
        int n = chalk.length;
        long[] sum = new long[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + chalk[i - 1];
        k %= sum[n];
        int l = 0, r = chalk.length;
        while (l < r) {  // 找到大于k的第一个数
            int mid = l + r >> 1;
            if (sum[mid] > k) r = mid;
            else l = mid + 1;
        }
        return r - 1;
    }

    public static void main(String[] args) {

        int[] chalk = {5, 1, 5};
        System.out.println((new Solution()).chalkReplacer(chalk, 22));
    }
}
